/**
 * 301. 删除无效的括号
 * https://leetcode-cn.com/problems/remove-invalid-parentheses/
 */
const { displayBaseArray } = require('../../libs/public');

const codeLeft = '('.charCodeAt(0);
const codeRight = ')'.charCodeAt(0);

let stack;
let top;

/**
 * @param {string} s
 * @return {boolean}
 */
function isValid(s) {
  top = -1;
  for (let i = 0; i < s.length; i += 1) {
    const code = s.charCodeAt(i);
    if (code === codeLeft) {
      top += 1;
      stack[top] = code;
    } else if (code === codeRight) {
      if (top >= 0 && stack[top] === codeLeft) {
        top -= 1;
      } else {
        top += 1;
        stack[top] = code;
      }
    }
  }
  return top < 0;
}

let result;

/**
 * @param {string} preS
 * @param {string} nextS
 * @param {number} leftToDelete
 * @param {number} rightToDelete
 */
function resolve(preS, nextS, leftToDelete, rightToDelete) {
  if (!nextS.length) {
    if (!leftToDelete && !rightToDelete) {
      if (isValid(preS)) {
        result.add(preS);
      }
    }
    return;
  }
  if (!leftToDelete && !rightToDelete) {
    const str = preS + nextS;
    if (isValid(str)) {
      result.add(str);
    }
    return;
  }
  let firstParenIndex = 0;
  for (; firstParenIndex < nextS.length; firstParenIndex += 1) {
    const code = nextS.charCodeAt(firstParenIndex);
    if (code === codeLeft || code === codeRight) {
      break;
    }
  }
  resolve(preS + nextS.substring(0, firstParenIndex + 1), nextS.substr(firstParenIndex + 1), leftToDelete, rightToDelete);
  if (nextS.charCodeAt(firstParenIndex) === codeLeft) {
    if (leftToDelete > 0) {
      resolve(preS + nextS.substring(0, firstParenIndex), nextS.substr(firstParenIndex + 1), leftToDelete - 1, rightToDelete);
    }
  } else {
    // eslint-disable-next-line no-lonely-if
    if (rightToDelete > 0) {
      resolve(preS + nextS.substring(0, firstParenIndex), nextS.substr(firstParenIndex + 1), leftToDelete, rightToDelete - 1);
    }
  }
}

/**
 * @param {string} s
 * @return {string[]}
 */
function removeInvalidParentheses(s) {
  let invalidLeftCount = 0;
  let invalidRightCount = 0;
  stack = new Array(s.length).fill(0);
  top = -1;
  for (let i = 0; i < s.length; i += 1) {
    const code = s.charCodeAt(i);
    if (code === codeLeft) {
      top += 1;
      stack[top] = code;
    } else if (code === codeRight) {
      if (top < 0) {
        invalidRightCount += 1;
      } else {
        top -= 1;
      }
    }
  }
  invalidLeftCount = top + 1;
  result = new Set();
  resolve('', s, invalidLeftCount, invalidRightCount);
  return Array.from(result);
}

console.log(displayBaseArray(removeInvalidParentheses('()())()')) === '[()()(),(())()]');
console.log(displayBaseArray(removeInvalidParentheses('(a)())()')) === '[(a)()(),(a())()]');
console.log(displayBaseArray(removeInvalidParentheses(')(')) === '[]');
